package main.java.com.itlin.datastructure.hashtable;

public class HashTable {

    //节点类
    public static class Entry{
        int hash; //哈希码
        Object key; //键
        public Object value; //值
        public Entry next; //指向下一个节点


        Entry(int hash,Object key,Object value){
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }

    public Entry[] table = new Entry[16]; //哈希表
    public int size = 0; //元素个数
    float loadFactor = 0.75f; //负载因子   16 * 0.75 = 12（阈值）
    int threshold = (int)(16 * loadFactor); //阈值

    /*
     *  求模运算替换为位运算
     *    - 前提： 数组长度必须为2的幂
     *    - 原理： 数组长度为2的幂，那么其二进制表示中只有一位是1，其余位都是0
     *    - hash % 数组长度  等价于  hash & (数组长度 - 1)   这是位运算
     */

    // 根据hash 码 获取 value
    Object get(int hash, Object key){
        int idx = hash & (table.length - 1);// 定位到 链表所在的索引
        //查询key
        if(table[idx] == null){
            return null;
        }
        Entry p = table[idx];
        while(p != null){
            if(p.key.equals(key)){ // 对象比较用equals
                return p.value;
            }
            p = p.next;
        }
        return null;
    }


    // 向hash表中添加元素  如果 key重复， 则更新value
    public void put(int hash, Object key, Object value){
        int idx = hash & (table.length - 1);// 定位到 链表所在的索引
        // 1. idx 处有空位， 直接新增
        if(table[idx] == null){
            // 1. idx 处有空位， 直接新增
            table[idx] = new Entry(hash,key,value);
        }else {
            //2. idx 处无空位，沿着链表查找，有重复的key，则更新value， 无重复的key， 则新增
            //定义一个指针
            Entry p = table[idx];
            // 链表要想新增，需要记录前一个节点的位置
            Entry prev = null;
            while(p != null){
                prev = p;
                if(p.key.equals(key)){
                    p.value = value;
                    return;
                }
                p = p.next;
            }
            // 3. 链表遍历结束， 没有找到key， 则新增
            prev.next = new Entry(hash,key,value);
        }
        size++;
        if(size >= threshold){
            resize(); //扩容
        }
    }

    private void resize() {
        // 1. 创建新数组
        Entry[] newTable = new Entry[table.length << 1];
        for (int i = 0; i < table.length; i++) {
            Entry p = table[i];// 拿到每个链表头
            if (p != null){
                // 拆分链表， 移动到新数组
                /*
                    拆分规律
                    * 旧数组中的一个链表最多拆成新数组中的两个链表
                    * hash & table.length == 0 的一组
                    * hash & table.length ！= 0 的一组

                    p
                    0 -> 8 -> 16 - > 24 - > 32 - > 40 -> 48 -> null

                    a

                    b
                 */
                Entry a = null;
                Entry b = null;
                Entry aHead = null;
                Entry bHead = null;
                while(p != null){
                    if((p.hash & table.length) == 0){
                        if (a != null){
                            a.next = p;
                        } else {
                            aHead = p;

                        }
                        // 分配到a 链表
                        a = p;
                    }else {
                        if (b != null){
                            b.next = p;
                        }else{
                            bHead = p;
                        }
                        // 分配到b链表
                        b = p;
                    }
                    p.next = null;// 切断链表
                    p = p.next;
                }
                // 将a链表和b链表 重新分配到新数组中
                // 规律： a 链表保持索引位置不变， b链表索引位置+table.length
                if (a != null){
                    a.next = null;
                    newTable[i] = aHead;
                }
                if (b != null){
                    b.next = null;
                    newTable[i + table.length] = bHead;
                }

            }
        }
        table = newTable;
        threshold = (int) (newTable.length * loadFactor);
    }

    //根据hash 码 删除元素
    public Object remove(int hash, Object key){
        int idx = hash & (table.length - 1); // 定位到链表所在的索引
        // 1. idx 处的链表为空，直接返回
        if(table[idx] == null){
            return null;
        }
        // 2. idx 处有元素，遍历链表
        Entry p = table[idx];
        // 链表要想删除，需要记录前一个节点的位置
        Entry prev = null;
        while(p != null){
            if(p.key.equals(key)){ // 对象比较用equals
                // 找到key， 删除
                // 1. 如果删除的是第一个元素，则直接将table[idx]指向下一个节点
                if (prev == null){
                    table[idx] = p.next;
                }else {
                    prev.next = p.next;
                }
                size--;
                return p.value;
            }
            prev = p;
            p = p.next;
        }
        return null;
    }


    public Object get(Object key){
        int hash = hash(key);
        return get(hash, key);
    }

    public void put(Object key, Object value){
        int hash = hash(key);
        put(hash, key, value);
    }

    public Object remove(Object key){
        int hash = hash(key);
        return remove(hash, key);
    }



    private static int hash(Object key) {
        int hash = key.hashCode();
        return hash;
    }
}
